Compute the sum of every possible subarray and store the maximum.
The complexity is given by the two nested for loops

Kadane's Algorithm is based on two observations:

1. the sum of values in any prefix of the optimal subarray is positive
2. the element before the first element of the optimal subarray is negative

kadane_algorithm(a[])
	n = a.length()
	max = Integer.MIN_VALUE
	sum = 0
	
	for i = 0 to n
		if sum > 0 
			sum += a[i]
		else 
			sum = a[i]

		max = Math.max(sum, max)
		
	return max
Copy

Example:

For each element find the highest bar to its left and right. Take the smaller of the two bars and call it . The difference between the height of the current bar and the is the amount of water that can be stored over the current bar.

The point is to think locally, not globally.
We compute two support arrays, the array of left and right leaders.

An element of an array is a right leader if it is greater than or equal to all the elements to its right side. The rightmost element is always a leader. Left leaders are analogous.
Computing leaders cost : to compute the right leaders traverse the array backwards.

We then have that:

• contains the left leader for the position
• contains the right leader for the position

The water that can be stored over the element is given by
we can then compute the sum with just one pass over .

Idea based on the previous solution plus the observation that we do not need all the leaders, but just the two currently meaningful leaders.

max_water(heights[]) 
	n = heights.length()
	left = 0, right = n-1
	result = 0

	left_max = 0 // max height seen by "left" so far, curr LL
	right_max = 0 // max height seen by "right" so far, curr RL

	while left < right 
		if heights[left] < heights[right] // shift "left"
			if heights[left] > left_max 
				left_max = heigths[left] // cant store water
			else 
				// add to the result the amount of warer
				// that can be kept over the position left
				result += left_max - heights[left]
			left += 1
		else // shift right
			if heights[right] > right_max 
				right_max = heights[right] // cant store water
			else 
				result += right_max - heights[right]
			right -= 1

	return result
Copy

We have a non-negative integer and we want to compute the square root of down to its nearest integer.
We can use the previous approach as:

• the answers fall in the interval
• the predicate is monotone

Hence we can simply call rangeBS(0, v, p) and return the smallest element that verifies the predicate.

Consider a sequence of mutually-disjoint intervals.
The extremes of each interval are non-negative integers.
We aim to find integer points within the intervals such that the smallest distance between consecutive selected point is maximized.

If a certain distance is feasible (i.e., exists a selection of points at that distance), then any smaller distance is also feasible. The feasibility is a monotone boolean predicate.
As the candidate answers range from to , where is the overall length of the intervals, the solution takes evaluations of the predicate.

What's the cost of evaluating the predicate?
We sort the intervals by their left endpoints and then evaluate any candidate distance
by scanning the sorted intervals from left to right.
First we select the left extreme of the first interval as the first point.
Then we move over the intervals and we choose greedily points at a distance at least from the previous one.
Thus an evaluation of the predicate takes time.

The total running time is .

pred(intervals, distance, c) {
	// the first point is the start of the first interval
	lastSelected = intervals[0].start 
	counter = 1
	// for every interval in intervals
	for i in intervals
		// we select as many points as we can in every interval.
		// we get the max using i.start because if a point falls
		// in the empty space between two intervals we place it 
		// at the start of the current interval
		while Math.max(lastSelected + distance, i.start) <= i.end
			lastSelected = Math.max(lastSelected + distance, i.start)
			counter++
	
	// returns true if we placed at least c points
	return counter >= c
}
socialDistancing(intervals, c) {
	// l is the maximum length of an interval
	if l < c
		return -1 // there is no solution

	// sort the intervals by the start
	intervals.sort()
	
	// do a tailored rangeBS on all the candidate answers
	// for each of them compute the predicate
	rangeBS(1, l+1, pred)
}
Copy

The obvious approach is to reuse the solution of the problem seen before.
For every node x we compute:

• max sum x.left-to-leaf path
• max sum x.right-to-leaf path
• take the maximum between the two
• add the value stored in x
• if this sum is greater than the current maximum then we update it

For every node x we call twice maxLeafRootPath. Since the function cost we have that the overall time complexity is .

We can find the maximum sum using a single traversal of binary tree.
The idea is to maintain two values in every recursive call:

1. maximum sum leaf-to-root path for the subtrees rooted under the current node
2. maximum path sum between leaves, the desired output

To solve the problem we use a custom post-order visit maxPathSum that exploits a global variable maxSum to store the result.
Our visit maxSumPath receive in input the root of the tree and then

• if the passed root is null we return
• left = maxSumPath(root.left), we recur on the left subtree
  • the function returns the sum of the path from the root to a leaf, hence left is the path sum from the current node to a leaf
• right = maxSumPath(root.right), we recur on the right subtree
• maxSum = Math.max(left+right+root.value, maxValue), update the maxSum if we found a bigger path from leaf to leaf passing for the current node

The following snippets further clarifies the algorithm:

maxValue = 0

solution(root)
	maxPathSum(root)
	print(maxValue)

// calculates two things:
// 1) maximum path sum between two leaves, which is stored in maxValue.
// 2) max current-node-to-leaf path sum, which is returned.
maxPathSum(node)
	if node == null
		return 0

	left = maxPathSum(node.left)
	right = maxPathSum(node.right)
	
	maxValue = Math.max(maxValue, left+right+node.value)

	return Math.max(left, right) + node.value
Copy

In "one pass" (aka one traversal) we do what we did in the trivial solution.
The reasoning is the following:

• Take a node x
• Compute the max path sum from x.left to a leaf i and the max sum path from x.right to a leaf j.
• The sum path from i to j, that passes through x, is greater than the one previously stored? Then we update the max

The result is maxValue when the program terminates.

Scan the array twice and we return true if we find two numbers that adds up to x

pairSum(a[], x)
	n = a.length()
	for i = 0 to n
		for j = i+1 to n
			if a[i] + a[j] == x
				return true
			if a[i] + a[j] > x
				break // a is sorted, need a new "i"
	return false
Copy

We use two pointers, left and right, to find the solution.
The pointer left will point to the first element of the array, and right to the last.
If the sum of the elements pointed by left and right is greater than x we will shift backwards by one right, in the other case we shift left one position to the right.
The solution takes advantage of the sortedness of the array.

pairSum(a[], x)
	n = a.length()
	left = 0, right = n-1

	while left < right
		if a[left] + a[right] == x
			return true
		if a[left] + a[right] < x
			left++
		else 
			right++

	return false
Copy

The trivial approach is to consider each of the n-k+1 windows independently.
For each window we compute its maximum by scanning it completely, which takes
We do that for each element of the array, hence

The problem in this approach is that we do not use the result of previous windows to compute the maximum of the current one.

To solve efficiently this problem we need a data structure that handle the next window while using the progress made in processing the previous one.

Notice that:

1. We can represent a window as a multiset of size k. In this setting the result for the current window is simply the biggest element in
2. When we move to the next window only two elements change: the first element of the window exist and the a new one enters as the last. Said easy: the window slides one position through the right.

We then require a data structure capable of performing three operations on a (multi)set:

• insert a new element
• delete an arbitrary element
• retrieve the maximum element

A BBST supports the three operations in , and it is optimal in the comparison model (lowest possible complexity in terms of comparison).
We can then solve the problem in time:

• insert the first k elements of the array in the tree and store the maximum
• iterate until we have covered all the windows:
  • shift the window
    • remove the leftmost element of the window
    • insert the new rightmost element in the window
  • store the maximum
• return the maximums

A heap is a tree-based data structure that satisfy the heap property:

• max-heap: for any given node C, if P is a parent of C than the key of P is than the key of C
• min-heap: the key of P is than the key of C

The main operations of a heap are:

• insert,
  • insert the new element at the bottom of the heap (next available position)
  • heapify-up: swap the element with its parent until the heap property is satisfied again
• remove min/max,
  • remove the root element, the mix or max of the tree
  • replace the root with the last element in the heap
  • heapify-down: swap the element with one of its children until the heap property is satisfied again
• peek,
  • return the maximum (or the minimum) without removing it

The solution can be then found using a max-heap and scanning through the array left to right:

• populate the max-heap with the first k elements, along with their respective positions
• as we move on to process the remaining elements one-by-one, we insert each current element with its position. We then request the heap to provide the current maximum: if it is paired with an index that is outside the window we discard it and ask again until we get it right

We insert elements with their respective index so that we can now if it is part of the window or not.
If the index of an element in the tree is smaller than i - (k-1), where i is the current iteration index, then the element is outside the window.

Using the above approach we have n insertions and at most n extractions of the maximum (window of size ).
Since the maximum number present in the heap at any given time is up to n, each of these operations takes time.
The overall complexity is .

The BST solution can do more than what is requested, e.g. we can have the second largest element in the window.
The fact that we can do much more than what is requested, it’s an important signal to think that a faster solution could exist.

The best solution uses a deque, a double-ended queue, which supports constant time insertion, removal and access at the front and back of the queue.

The algorithm behaves as follows:

1. Iterate through the array, one element at a time
2. While processing each element we maintain a deque Q that store only elements that are relevant for the current window. Specifically: Q stores only elements that are maximum candidates for the current and for future windows.
3. At each step we do:
   1. Remove elements from the front of Q that are outside the current window. This is done by checking if the indices of those elements are beyond the current window boundary
   2. Remove elements from the back of Q that are to the current element. Those elements cannot be the maximum within the current or any future windows and we only keep elements that might become maximum elements for a window
   3. Append the index of the current element to the back of Q, as it could be a maximum element in the current or future windows
4. Once we have processed all the elements and maintained the deque as described, the maximum element for each window are stored in the front of the deque, collect these values and return them as result

// q = [a, ..., z]
//      front    back
//      head     tail
slidingWindowMaximum(a[]) 
	n = a.length()
	Deque q
	maxs[n-k+1]

	// first window
	for i = 0 to k 
		while !q.isEmpty() && a[i] > a[q.back()]
			q.popBack()
		q.pushBack(i)

	maxs.push(a[q.front()]);

	for i = k to n 
		// remove elements that dont belongs in the window
		while !q.isEmpty() && q.front() + k <= i
			q.popFront()

		// remove elements that are smaller that the current element
		// as this elements cannot be the maximum for this window nor 
		// for future windows
		while !q.isEmpty() && a[i] > a[q.back()]
			q.popBack()
		q.pushBack(i)
		
		maxs.push(a[q.front()])

	return maxs;
Copy

What is the complexity of the algorithm?
Let's consider the following costs:

• Identifying the range of points with the required y-coordinates takes
• Removing a point takes
• Iterating over the points in this range takes constant time per point
• How many points we do iterate over? There can be at most 8 points that have an x-coordinate greater or equal to and therefore survive.
• There can be many points with smaller x-coordinates. However since each point is inserted and subsequently removed from the set (BST) of points at most once during the execution, the cost of dealing with all these points is at most

1. Start at the root node: Begin traversal from the root of the BBST.
2. Recursively traverse the tree:
   • If the current node's key falls within the given range, add it to the result
   • If the current node's key is smaller than the range, recursively search the right subtree
   • If the current node's key is larger than the range, recursively search the left subtree
3. Continue until a base case is reached:
   • If the current node is NULL, stop the traversal
   • If the current node's key is outside the given range, prune the subtree and stop traversal in that direction
4. Return the result:
   • Accumulate all nodes within the range while traversing the tree
   • Return the collected nodes as the result

The overall complexity is therefore .

Check that every integer x [left, right] is covered by at least one interval in ranges

isCovered(ranges, left, right) 
	for i = left to right 
		covered = false // i is not covered until proven otherwise
		for range in ranges 
			if i >= range.start && i <= range.end 
				covered = true // i is covered by the current interval
				break;
			
		// if i is not covered then we return false
		if covered == false 
			return false
	
	// each i in [left, right] is covered by at least one range
	return true;
Copy

We use sweep line and a map to solve the problem.

isCovered(ranges, left, right)
	// map: point i -> number of open ranges in i
	HashMap openRangesAt
	for range in ranges 
		openRangesAt.insert(openRangesAt.getOrDefault(range.start, 0) + 1)
		// range.end+1 as the ranges are inclusive!
		openRangesAt.insert(openRangesAt.getOrDefault(range.end+1, 0) - 1)

	openRangesNow = 0
	for i = 0 to left 
		openRangesNow += openRangesNow.getOrDefault(i, 0)

	for point=left to right 
		openRangesNow += openRangesNow.getOrDefault(point, 0)
		if openRangesNow == 0
			return false

	return true
Copy

Consider a string consisting only of characters and .
We need to answer queries.
Each query where asks for the number of positions such that .

Consider the following example (-indexing):

• • the substring is
  • the positions 3, 4 and 6 make true , but do not count since

To solve the problem we can use the prefix sums.
We can compute the binary array such that
At this point the answer to the query is .
Now every query can be solved in constant time by computing the prefix sum array of the vector .
Let's call the prefix sum array of : we have that .

We are given an array and a set of queries. Each query is a range sum, the query returns the sum of the elements in .
The goal is to permute the elements in in order to maximize the sum of the results of the queries in .

The key is to observe that if we want to maximize the sum we have to assign the largest values to the most frequently accessed entries.
Hence the solution consists in sorting in descending order, then sort in descending order the frequency of access of every element and pair the two.
Once we have computed the frequencies the solution takes .

We are left with the problem of computing the frequencies.
We want to compute an array where  is the number of times the index 
belongs to a query of .
Computing this array by updating every entry of for every query takes , and thus is unfeasible.
We can solve this problem using the prefix sum.

Let's consider an array such that its prefix sums are equal to our target array .
We need to only modify two entries of to account for a query of .
This is done as follows:

• set all the entries of to
• for every query we do
  • ++
  • --
• the prefix sum of is
  • unchanged for the indexes less than
  • increased by one for the indexes in
  • unchanged for the indexes greater than

Therefore the prefix sum of up to is equal to .
This algorithm takes time: we have queries to go through, plus , which is the time needed to build and its prefix sum array.

The code clarifies the algorithm:

littleGirlMax(a[], q[]) 
	n = a.length()
	
	u[n] // compute U
	for (l, r) in q
		u[l]++
		if r + 1 < n 
			u[r+1]--

	f[n] // compute the prefixSum of U, aka F
	pS = 0
	for i = 0 to n
		pS += u[i]
		f[i] = pS

	// sort the array and the frequencies in decreasing order
	a.sortDecreasing()
	f.sortDecreasing()

	// return the maximized sum of the queries
	res = 0
	for i = 0 to n
		res += a[i] * f[i]

	return res
Copy

Given an array count the number of times the array can be divided into three subarrays that have the same sum.
Formally we need to find the number of pairs of indices (with ) such that: Let's say that the sum of the whole array is .
If cannot be divided by we immediately return .

Then we compute an array that stores, at position , the number of suffixes of the suffix that sums up to .
starts with every entry set to , then:

if A[n] == S/3
	C[n] = 1

// iterate through A[] backwards to fill up C
suffixSum = A[n]
for i = n-1 to 1
	suffixSum += A[i]
	if suffixSum == S/3 
		C[i] = C[i+1] + 1
	else 
		C[i] = C[i+1]
Copy

At this point we scan left to right to compute its prefix sum.
Every time the prefix sum at position is we add to the result.
This is because the part sums up and can be combined with any pair of parts of that also sums up to .
Since the values in sums to , the number of such pairs is the number of suffixes that sums to in .

Clarification: because we want three partitions, if you were to use you could use the whole remaining whose elements sums to  , and you would get only two partitions.

Said Easy:

• say that you have
• the prefix sum array of is represented with
• iterate using the index
  • is ?
    • then we have found one of the three parts that summed give
    • the number of suffixes of the suffix are the third part
      • if the whole sum up to than we have found the three parts:
      • counting the other suffixes makes it work: we are counting the indexes such that we can decompose in three parts, counting the s is as counting the s

From each element i in the array we compute every possible subarray starting in i and check that the sum of the elements of the subarray is a multiple of k, storing the maximum length so far.

The solution is based on a math property:

1. any two prefix sums that are not next to each other and have the the same value mod implies that there is a good subarray (the subarray between the last element of the first subarray and the first element of the second one)
2. a prefix sum with mod that is not the first number will, yield a valid subarray.

The algorithm then is as follows:

checkSubarraySum(array, k)
	n = array.length()
	
	prefixSumArray[] // prefix sum array
	pS = 0
	for i = 0 to n
		pS += array[i]
		prefixSumArray[i] = pS

	// map: modulo -> index i st prefixSumArray[i] % k = modulo
	HashMap modsToIndices
	for (i, prefixSum) in prefixSumArray.enumerate() 
		modulo = prefixSum % k

		// if modulo is 0 and not the first ok
		if modulo == 0 && i != 0 
			return true

		// first time we see this modulo
		if modsToIndices.contains(modulo) == false
			modsToIndices.insert(modulo, i)
		else 
			// this modulo has been seen
			previousIndex = modsToIndices.get(modulo);
			// not the previous
			if previousIndex < i - 1
				return true

	return false
Copy